package org.example.util;

import lombok.Data;

@Data
public class DisJointSet {

    private int n;

    private int[] pre;

    public DisJointSet(int n) {
        this.n = n;
        pre = new int[n + 1];
        init();
    }

    public void init() {
        for (int i = 0; i <= n; ++i) {
            pre[i] = i;
        }
    }

    public int find(int x) {
        if (x != pre[x])
            pre[x] = find(pre[x]);
        return pre[x];
    }

    public void join(int x, int y) {
        int fx = find(x);
        int fy = find(y);
        if (fx != fy) {
            pre[fx] = fy;
        }
    }

}
